#include <bits/stdc++.h>
using namespace std;

/*
1488. 避免洪水泛滥
已解答
中等
相关标签
premium lock icon
相关企业
提示
你的国家有无数个湖泊，所有湖泊一开始都是空的。当第 n 个湖泊下雨前是空的，那么它就会装满水。如果第 n 个湖泊下雨前是 满的 ，这个湖泊会发生 洪水 。你的目标是避免任意一个湖泊发生洪水。

给你一个整数数组 rains ，其中：

rains[i] > 0 表示第 i 天时，第 rains[i] 个湖泊会下雨。
rains[i] == 0 表示第 i 天没有湖泊会下雨，你可以选择 一个 湖泊并 抽干 这个湖泊的水。
请返回一个数组 ans ，满足：

ans.length == rains.length
如果 rains[i] > 0 ，那么ans[i] == -1 。
如果 rains[i] == 0 ，ans[i] 是你第 i 天选择抽干的湖泊。
如果有多种可行解，请返回它们中的 任意一个 。如果没办法阻止洪水，请返回一个 空的数组 。

请注意，如果你选择抽干一个装满水的湖泊，它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊，那么将无事发生。

 

示例 1：

输入：rains = [1,2,3,4]
输出：[-1,-1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，装满水的湖泊包括 [1,2,3]
第四天后，装满水的湖泊包括 [1,2,3,4]
没有哪一天你可以抽干任何湖泊的水，也没有湖泊会发生洪水。
示例 2：

输入：rains = [1,2,0,0,2,1]
输出：[-1,-1,2,1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，我们抽干湖泊 2 。所以剩下装满水的湖泊包括 [1]
第四天后，我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。
第五天后，装满水的湖泊包括 [2]。
第六天后，装满水的湖泊包括 [1,2]。
可以看出，这个方案下不会有洪水发生。同时， [-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的方案。
示例 3：

输入：rains = [1,2,0,1,2]
输出：[]
解释：第二天后，装满水的湖泊包括 [1,2]。我们可以在第三天抽干一个湖泊的水。
但第三天后，湖泊 1 和 2 都会再次下雨，所以不管我们第三天抽干哪个湖泊的水，另一个湖泊都会发生洪水。
 

提示：

1 <= rains.length <= 105
0 <= rains[i] <= 109
*/

// 法一 
class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        vector<int> ans(n, -1);     // 结果数组：雨天默认-1，晴天后续赋值
        unordered_map<int, int> lastRain;    // 记录湖泊上次下雨的日期：key=湖泊号，value=日期
        set<int> dryDays;           // 存储未使用的晴天日期
        for (int i = 0; i < n; i++) {
            if (rains[i] > 0) {
                // 当天是雨天：处理对应湖泊
                int lake = rains[i];
                if (lastRain.count(lake)) {
                    // 该湖泊之前下过雨，需找两次下雨之间的晴天抽干
                    int prevRainDay = lastRain[lake];  // 上次下雨的日期
                    // 找第一个 > prevRainDay 的晴天（确保在两次下雨之间）
                    auto it = dryDays.upper_bound(prevRainDay);
                    
                    // 无可用晴天（要么没晴天，要么晴天在本次下雨之后）→ 洪水无法避免
                    if (it == dryDays.end() || *it >= i)  return {};

                    // 使用找到的晴天抽干该湖泊
                    int targetDryDay = *it;  // 修复：变量名改为targetDryDay，避免与set重名
                    ans[targetDryDay] = lake;  // 标记该晴天抽干的湖泊
                    dryDays.erase(it);         // 从可用晴天中移除（已使用）
                }
                // 更新该湖泊最近一次下雨的日期
                lastRain[lake] = i;
                // ans[i] = -1;  // 初始化已设为-1，可省略
            } else {
                // 当天是晴天：暂存入可用晴天集合，后续等待分配抽干任务
                dryDays.insert(i);
                ans[i] = 1;  // 临时值：未被分配的晴天抽干任意湖泊（不影响结果）
            }
        }
        return ans;
    }
};

// 法二
class Solution {
public:
    // 并查集查找（路径压缩）：找到当前节点的根节点
    int find(int fa[], int i) {
        return (fa[i] == i) ? i : (fa[i] = find(fa, fa[i]));
    }
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        int fa[n];         // 并查集：管理连续雨天的分组（根节点为最左雨天）
        int idx[n];        // 记录每个雨天组（根节点标识）对应的下一个可用晴天索引
        unordered_map<int, int> occur;  // 记录湖泊上次下雨的日期（索引）
        vector<int> res(n, 1);          // 结果数组：晴天默认1，雨天设为-1
        for (int i = 0; i < n; ++i) {
            if (rains[i]) {  // 处理雨天
                // 合并连续雨天：若前一天也是雨天，当前雨天归为前一天的组
                if (i && rains[i-1]) {
                    fa[i] = fa[i-1];
                } else {
                    // 新的雨天组：根节点为自身，暂标记无可用晴天（idx设为大值）
                    fa[i] = i;
                    idx[i] = 1000000;  // 初始值表示暂无可用晴天
                }
                // 若该湖泊之前下过雨，检查是否有晴天可抽干
                if (occur.count(rains[i])) {
                    int last = occur[rains[i]];  // 上次下雨的索引
                    int f = find(fa, last);      // 找到上次下雨所在组的根节点
                    // 若该组无可用晴天（或晴天在本次下雨之后），洪水不可避免
                    if (idx[f] >= i) return {};
                    // 使用该组的可用晴天抽干湖泊，更新下一个可能的晴天索引
                    res[idx[f]++] = rains[i];
                    // 若新的晴天索引仍是雨天，合并两个雨天组
                    if (idx[f] < n && rains[idx[f]]) {
                        fa[f] = find(fa, idx[f]);
                    }
                }
                // 更新该湖泊最近下雨日期，标记当前雨天结果为-1
                occur[rains[i]] = i;
                res[i] = -1;
            } else if (i && rains[i-1]) {  // 处理晴天，且前一天是雨天
                // 为前一天所在的雨天组标记可用晴天
                idx[find(fa, i-1)] = i;
            }
        }
        return res;
    }
};